package com.laotang.第_2_章_二维数组.力扣_289_生命游戏;

public class _289_game_of_life {
    // 方案二：原地更新
    // 时间复杂度：O(mn)
    // 空间复杂度：O(1)
    public void gameOfLife(int[][] board) {
        int[][] directions = {
                {-1, 0}, {1, 0}, {0, -1}, {0, 1},
                {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
        };

        int m = board.length;
        int n = board[0].length;

        // 遍历每个细胞，并确定它最终的状态
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;
                for (int[] dir : directions) {
                    int nextRow = row + dir[0];
                    int nextCol = col + dir[1];
                    if (nextRow < m && nextCol < n && nextRow >= 0 && nextCol >= 0) {
                        if (Math.abs(board[nextRow][nextCol]) == 1) liveNeighbors++;
                    }
                }
                // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                    board[row][col] = -1;
                // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

                // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

                // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                if (board[row][col] == 0 && liveNeighbors == 3) board[row][col] = 2;
            }
        }

        // 遍历 board 得到一次更新后的状态
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }

    // 方案一：使用辅助数组
    // 时间复杂度：O(mn)
    // 空间复杂度：O(mn)
    public void gameOfLife1(int[][] board) {
        int[][] directions = {
                {-1, 0}, {1, 0}, {0, -1}, {0, 1},
                {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
        };

        int m = board.length;
        int n = board[0].length;

        // 创建复制数组 copyBoard
        int[][] copyBoard = new int[m][n];

        // 从原数组复制一份到 copyBoard 中
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        // 遍历每个细胞，并确定它最终的状态
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;
                for (int[] dir : directions) {
                    int nextRow = row + dir[0];
                    int nextCol = col + dir[1];
                    if (nextRow < m && nextCol < n && nextRow >= 0 && nextCol >= 0) {
                        if (copyBoard[nextRow][nextCol] == 1) liveNeighbors++;
                    }
                }
                // 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                if (copyBoard[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                    board[row][col] = 0;
                // 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

                // 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

                // 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                if (copyBoard[row][col] == 0 && liveNeighbors == 3) board[row][col] = 1;
            }
        }
    }
}
